\chapter{Tas Binaire}
L'une des structure à implémenter était les arbres binaire.
\section{Analyse}
Les tas sont des structures de données arborance d'abre équilibré c'est-a-dire le hauteur de ce dernier est au plus égal à $2^n$ (n étant le nombre de n\oe{}uds). De plus les n\oe{}uds sont stocker de contigüe dans un tableau.

Les n\oe{}uds sont agacer de la manière suivante:

\paragraph{}-- Soit A et B deux  n\oe{}uds du tas, si $B$ est le fils de $A$: 
		
			\[ valeur(A) >= valeur(B)\]
			
	Exemple:
	
	
	Les tas sont souvant utliser pour pour implémenter des files de priorité , ainsi que les trie par tas.
	

De plus le tas devait être générique tous comme les conteneur de la {\sc STL} c'est-a-dire, qu'il devait être capable de stocker n'importe quel type d'objet et avec n'importe quelle type de comparateur.	
\section{Implementation}
Pour l'implémentation de la structure plusieurs choix étais possible.
\paragraph{Choix n°1}
  Ce choix  consiste a encapsuler les valeur dans une structure récursive {\tt Node}:
\begin{verbatim}
 Struc Node<T>{
  T value
  Node<T>* pere;
  Node<T>* fils_gauche;
  Node<T>* fils_droit;
}
\end{verbatim}

Avec une tel structure tous n\oe uds accède a sont père a sont et à ses 2 fils de façon direct. 

Si un n\oe{}eud n n'as pas de fils alors le pointer associer au fils sera a \verb+Null+.
Si un n\oe{}ud est une racine la valeur du pointeur vers sont père sera également \verb+Null+

\paragraph{Choix n°2} 
Ce choix consiste stoker les valeurs dans un conteur indexé comme par exemple un tableau. L'accès aux fils et au père d'une valeur dans le tableau se fait par le biais d'une opération sur l'indice ou ce trouve cette dernière.

Exemple:
Soit une valeur est un indice $i$ alors:
\[
pere(i)=
  \left\{
      \begin{array}{lc}
	  \frac{i}{2}-1 & \mbox{si } i \mbox{ paire}\\
	  \frac{i}{2} & \mbox{sinon}\\
      \end{array}
    \right.
\]
De plus on a:
\[
 fils\_droit(i) = 2i+1
\]

\[
 fils\_gauche(i) = 2i+2
\]

\subsection{Choix Implémentation}

Nous avons choisie les solution {\bf n°2} car en effet elle plus la facile a mette en place et les {\sc STL} fournir le conteneur \verb+sdt::vector+ qui fournie un interface permettant d'accéder a des valeur stoquer grâce a des indice.  
 \section{Jeux d'essais }

